There are n hotels
along the beautiful Adriatic coast. Each hotel has its value in Euros.
Sroljo has
won m
Euros on the lottery. Now he wants to buy a sequence of consecutive hotels,
such that the sum of the values of these consecutive hotels is as great as
possible – but not greater
than m.
You are to
calculate this greatest possible total value.
Input. In
the first line there are integers n
and m (1 ≤ n ≤ 300 000, 1 ≤ m
< 231). In the next line there are n natural numbers less than 106, representing the hotel
values in the order they lie along the coast.
Output. Print the required number (it will be greater than 0 in all
of the test data).
|
Input |
Output |
|
5 12 2 1 3 4 5 |
12 |
последовательности – скользящее окно
Стоимости отелей занесем в массив a. Интервал [i … j] будем называть хорошим, если сумма стоимостей отелей на нем не больше m.
Реализуем скользящее окно при помощи двух индексов i и j и будем его поддерживать так, чтобы текущий
рассматриваемый интервал [i … j] был хорошим, а интервал [i – 1 … j] плохим. Пусть s – сумма стоимостей отелей на интервале [i … j]. Если s + a[j + 1] ≤ m, то расширяем текущий интервал до a[i.. j + 1].
Иначе сокращаем его до a[i + 1.. j]. Находим
максимум среди стоимостей всех рассматриваемых хороших интервалов.
Реализация
алгоритма
#include <stdio.h>
#define MAX 300010
int i, j, n;
long long res, m, s, a[MAX];
int main(void)
{
scanf("%d
%lld",&n,&m);
for (j = 0; j
< n; j++)
scanf("%lld",
&a[j]);
s = i = 0;
for (j = 0; j
< n; j++)
{
s += a[j];
while (s
> m) s -= a[i++];
if (s >
res) res = s;
}
printf("%lld\n",res);
return 0;
}
Реализация
алгоритма – STL, queue
#include <cstdio>
#include <queue>
using namespace std;
int i, j, n;
long long res, m, s, val;
queue<int> q;
int main(void)
{
scanf("%d
%lld",&n,&m);
for (s = i =
0; i < n; i++)
{
scanf("%d",&val);
q.push(val);
s += val;
while (s
> m)
{
s -= q.front();
q.pop();
}
if (s >
res) res = s;
}
printf("%lld\n",res);
return 0;
}